複製到陣列後使用雙指標法

解題思路

有兩種常見的 List 實作方式，分別是 ArrayList 和 LinkedList。它們在存儲值的方法上有什麼區別呢？

• ArrayList 是用一個連續的陣列來存儲值，我們可以直接通過 index 快速訪問任意位置的值，這是利用了記憶體的位址計算。
• LinkedList 是用一系列的節點來存儲值，每個節點包含一個值和一個指向下一個節點的指標。訪問某個特定位置的值需要從第一個節點開始，沿著指標逐個遍歷，這需要花費更多的時間。

判斷 ArrayList 是不是回文很簡單，我們可以用兩個指標分別從兩端向中間移動，比較對應位置的值是否相等。這個過程只需要 的時間，因為每個值都可以在 的時間內訪問，而列表有 個值。

但是同樣的方法在 LinkedList 上就不太方便，因為無論正向還是反向訪問值都不是 的時間。所以最簡單的方法就是先把 LinkedList 的值複製到一個 ArrayList 中，然後再用兩個指標法判斷是否是回文。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：1545)

演算法

這個演算法有兩個步驟：

1. 把 LinkedList 的值複製到一個 ArrayList 中。
2. 用兩個指標從兩端向中間比較 ArrayList 的值，看是否是回文。

第一步，我們從 LinkedList 的第一個節點開始，把每個節點的值加到 ArrayList 裡面。我們用一個變數 currentNode 來記錄目前訪問的節點。每次迭代時，我們把 currentNode 的值放到 ArrayList 中，然後把 currentNode 更新為下一個節點，直到 currentNode 為空為止。

第二步，我們用兩個變數 front 和 back 來表示陣列列表的左右指標。一開始，front 為 0，back 為陣列列表的長度減 1。每次迭代時，我們比較 front 和 back 指向的值是否相等，如果不等，就返回 false；如果相等，就把 front 加 1，back 減 1，並繼續比較，直到 front 大於等於 back 為止。

程式

class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val list = mutableListOf<Int>()
        var root = head
        head?.let {
            list.add(it.`val`)
            while (root?.next != null) {
                root?.next?.let {
                    root = it
                    list.add(it.`val`)
                }
            }

            var front = 0
            var back: Int = list.size - 1
            while (front < back) {
                if (list[front] != list[back]) {
                    return false
                }
                front++
                back--
            }
        }
        return true
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是 LinkedList 的元素個數。

• 第一步，我們遍歷 LinkedList 並把值複製到一個 ArrayList 中，這個過程需要 的時間。
• 第二步，我們用兩個指標從兩端向中間比較 ArrayList 的值，看是否是回文。這個過程需要比較 次，所以時間複雜度也是 。
• 總的時間複雜度是 ，根據 Big 符號的定義，常數項可以忽略不計，所以最終的時間複雜度是 。

• 空間複雜度:
  ，其中 是 LinkedList 的元素個數。我們使用一個 ArrayList 來存儲 LinkedList 的元素值，所以需要額外的 的空間來存儲這些值。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：1545)